/* 
 * File:   backtracking.cpp
 * Author: totito
 *
 * Created on April 2, 2014, 11:57 AM
 */

#include <cstdlib>
#include <iostream>
#include "Shape.h"
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <vector>
#include <map>
#include <string.h>

//Agregado por ricardo
#include <fstream>
#include <sstream>
#include <utility>
//#define dbug(format, ... ) printf (format, ## __VA_ARGS__)
#define dbug(format, ... ) 

using namespace std;
long double iteraciones=0;
int colores = 4;
int filas = 2;
int ultimoRetroceso=0;
int columnas = 2;
int mejorSolucionComodines = filas * columnas;
int comodinesActual = 0;
int minIntentos;
Shape* comodinAux;
Shape* debugAux;
//estas son las disponibles
list<Shape*> fichas;
//estas son para manejo de memoria
vector<Shape*> fichasM;
list<int> comodinesUsados;
vector<int> intentosPorPosicion;
vector<Shape*> tableroActual;
vector<Shape*> mejorTablero;
void printIntentos(void) {
    return;
    for (int t = 0; t < intentosPorPosicion.size(); t++) {
        if (t == minIntentos){
            dbug("_%d_|", intentosPorPosicion[t]);
        }else{
            dbug(" %d |", intentosPorPosicion[t]);
        }
    }
    dbug("\n");
}
void printFichas(void) {
    return;
    for (list<Shape*>::iterator it = fichas.begin(); it != fichas.end(); ++it) {
        dbug("%d %d %d %d\n", (*it)->left, (*it)->top, (*it)->right, (*it)->bottom);
    }
}

void printTablero(vector<Shape*> * tablero, int index = -1) {
    return;
    char defaultBackground[] = "_";
    char indexBackground[] = "@";
    char* currentBackground;
    int t=system("clear");
    for (int i = 0; i < filas; i++) {
        for (int t = 0; t < columnas * 4; t++) {
            dbug("-");
        }
        dbug("\n");
        for (int ii = 0; ii < 3; ii++) {
            for (int j = 0; j < columnas; j++) {
                if ((i * columnas + j) == index) {
                    currentBackground = indexBackground;
                } else {
                    currentBackground = defaultBackground;
                }

                for (int jj = 0; jj < 3; jj++) {
                    if (ii == 0 and jj == 0)
                        dbug("%s", currentBackground);
                    if (ii == 0 and jj == 2)
                        dbug("%s", currentBackground);
                    if (ii == 2 and jj == 0)
                        dbug("%s", currentBackground);
                    if (ii == 2 and jj == 2)
                        dbug("%s", currentBackground);
                    if (ii == 1 and jj == 1)
                        dbug("%s", currentBackground);
                    if (ii == 1 and jj == 0)
                        dbug("%d", (*tablero)[i * columnas + j]->left);
                    if (ii == 1 and jj == 2)
                        dbug("%d", (*tablero)[i * columnas + j]->right);
                    if (ii == 0 and jj == 1)
                        dbug("%d", (*tablero)[i * columnas + j]->top);
                    if (jj == 1 and ii == 2)
                        dbug("%d", (*tablero)[i * columnas + j]->bottom);
                }
                dbug("|");
            }
            dbug("\n");
        }
    }

    for (int t = 0; t < columnas * 4; t++) {
        dbug("+");
    }

    dbug("  current [%d]  mejor [%d] fichas disp [%d]\n", comodinesActual, mejorSolucionComodines, fichas.size());
    printIntentos();
    //dbug("                                              \n");
    //system("sleep 0.1");
}

void posicionarFicha(vector<Shape*> * tablero, int i, Shape *ficha) {
    (*tablero)[i] = ficha;
}

void* getIzquierda(vector<Shape*> * tablero, int i) {
    if ((i % columnas) != 0)
        return (*tablero)[i - 1];
    return comodinAux;
}

void* getArriba(vector<Shape*> * tablero, int i) {
    if (i >= columnas)
        return (*tablero)[i - columnas];
    return comodinAux;
}



int dameFichaQueEncaje(Shape* izquierda, Shape* arriba, Shape** ficha) {
    int otras = 0;
    Shape* elegida;
    for (list<Shape*>::iterator it = fichas.begin(); it != fichas.end(); ++it) {

        if ((*it)->fichaEncaja(izquierda, arriba)) {
            otras += 1;
            if (otras == 1) {
                elegida = *it;
            }
        }
    }
    if (otras > 0) {
        fichas.remove(elegida);
        *ficha = elegida;
        //        dbug("%d %d %d %d\n", elegida->left, elegida->top, elegida->right, elegida->bottom);
        //        dbug("otras %d\n", otras);
        return otras;
    } else {
        *ficha = comodinAux;
        return 1;
    }
}

void calcularSolucion(int i) {

    int posUltimoComodin;
    Shape* arriba;
    Shape* izquierda;
    Shape* fichaAux;

    while (true) {            

        iteraciones++;
        printIntentos();
        if (i >= columnas * filas) {
            //dbug("---------------------- paso  %d \n ", i);
            if (comodinesActual < mejorSolucionComodines) {
                mejorSolucionComodines = comodinesActual;
                mejorTablero = tableroActual;
                //dbug("---------------------- paso s %d \n ", i);
                if (comodinesUsados.size() > 0) {
              //      dbug("llegue al final busco mejor solucion");
                    //fixear
                    posUltimoComodin = comodinesUsados.back();
                    comodinesUsados.pop_back();
                    comodinesActual -= 1;
                    for (int t = posUltimoComodin; t < columnas * filas; t++) {
                        //debug("devuelvo fincha ")
                        intentosPorPosicion[t] = 0;
                        if (!tableroActual[t]->esComodin() and !tableroActual[t]->esDebug()) {
                            //dbug("devuelvo ficha %d ", fichas.size());
                            dbug("%d %d %d %d\n", (tableroActual[t])->left, (tableroActual[t])->top, (tableroActual[t])->right, (tableroActual[t])->bottom);
                            fichas.push_back(tableroActual[t]);
                        }
                        posicionarFicha(&tableroActual, t, debugAux);
                    }
                    i = posUltimoComodin - 1;
                    intentosPorPosicion[i] = 0;
                    printFichas();
                    printIntentos();
                    continue;
                } else {
                    //debug("solucion sin comodines !!!!!")
                    dbug("salgo en solucion sin comodines");
                    break;
                }
                //debug("cantidad de comodines %s" % mejorSolucionComodines)
                dbug("aca no tiene que salir nunca");
                break;

            }
        } else {
           // dbug("---------------------- paso  %d intento %d comodines %d  ", i, intentosPorPosicion[i], comodinesActual);
        }

        if (i < 0) {
            //   debug("cantidad de comodines %s end" % mejorSolucionComodines)
            dbug("salgo por retroceso  a i < 0");
            printTablero(&mejorTablero);
            break;
        }
        //###################################################33333
        if (intentosPorPosicion[i] == 0 and i != 0 ) {
            //avanzo en una rama
            izquierda = (Shape*) getIzquierda(&tableroActual, i);
            arriba = (Shape*) getArriba(&tableroActual, i);
            intentosPorPosicion[i] = dameFichaQueEncaje(izquierda, arriba, &fichaAux);
            //            dbug("%d %d %d %d\n", fichaAux->left, fichaAux->top, fichaAux->right, fichaAux->bottom);
        } else {
            //            			#tuve que volver hacia atras
            intentosPorPosicion[i] -= 1;
            if (intentosPorPosicion[i] <= 1) {
                if (i == 0) {
                    //dbug("cantidad de comodines %d end", mejorSolucionComodines);
                    printTablero(&mejorTablero);
                    dbug("salgo no hay mas intento en i == 0 ");
                    break;
                } else {
                    //#devuelvo la ficha anterior al las disponibles 
                    intentosPorPosicion[i] = 0;
                    if (tableroActual[i - 1]->esComodin()) {
                        comodinesActual -= 1;
                        //revisar
                        comodinesUsados.remove(i - 1);
                    } else {
                    //    dbug("devuelvo ficha %d ", fichas.size());
                        fichas.push_back(tableroActual[i - 1]);
                    }
                    posicionarFicha(&tableroActual, i, debugAux);
                    //					debug( string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], ''))
                    //					debug("------------------------------       retrocedo por intentos")
                    //					#encontrarTablero(i-1)

                    i = i - 1;
                    if (minIntentos > i )
                        minIntentos = i;
                    continue;
                    //      #return 
                }
            } else {
                izquierda = (Shape*) getIzquierda(&tableroActual, i);
                arriba = (Shape*) getArriba(&tableroActual, i);
                dameFichaQueEncaje(izquierda, arriba, &fichaAux);
            }
        }
        //################################################
        if (fichaAux->esComodin()) {
            //dbug("comodines actual %d comodines mejor %d ", comodinesActual, mejorSolucionComodines);
            if (comodinesActual + 1 >= mejorSolucionComodines) {
                //#devuelvo la ficha anterior al las disponibles 
                if ((tableroActual[i - 1])->esComodin()) {
                    comodinesActual -= 1;
                    comodinesUsados.remove(i - 1);
                } else {
                    //dbug("devuelvo ficha %d ", fichas.size());
                    fichas.push_back(tableroActual[i - 1]);
                }
                intentosPorPosicion[i] = 0;
                posicionarFicha(&tableroActual, i, debugAux);
                printTablero(&tableroActual, i);
                //debug(string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], ''))
                //dbug("-------------------------------  retrocedo  por comodin");
                //#intentosPorPosicion[i] = ficha[0]
                //#encontrarTablero(i-1)
                i = i - 1;
                continue;
                //#return 
            } else {
                posicionarFicha(&tableroActual, i, fichaAux);
                comodinesActual += 1;
                comodinesUsados.push_back(i);
                printTablero(&tableroActual, i);
                //debug(string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], '')	)
                //debug("=================================== pongo comodin")
                //#encontrarTablero(i+1)			
                //#return 
                i = i + 1;
                continue;
            }
        } else {
            posicionarFicha(&tableroActual, i, fichaAux);
            //#intentosPorPosicion[i] = ficha[0]
            printTablero(&tableroActual, i);
            //debug( string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], '')	)
            //dbug("###################################### pongo ficha");
            //#encontrarTablero(i+1)
            //#return 
            i = i + 1;

            continue;
        }

    }
 
}

void crearTableros(void) {
    mejorSolucionComodines = filas * columnas;
    intentosPorPosicion.resize(filas * columnas, 0);
    mejorTablero.resize(filas * columnas);
    tableroActual.resize((filas * columnas));

    for (int i = 0; i < filas * columnas; i++) {
        tableroActual[i] = debugAux;
    }
}
void releaseShapes(void) {
    //int t=system("clear");
    // for(int i=0; i<filas; i++){
    //     for(int j=0; j<columnas; j++){
        //    printf("%d ",mejorTablero[i*columnas+j]->id);
        // }
        //printf("\n");
    // }
    dbug("filas %d columnas %d NxM %d iteraciones %Lf\n",filas,columnas,filas*columnas,iteraciones);
    printf("NxM,iteraciones: %d,%Lf\n",filas*columnas,iteraciones);
    int s = fichas.size();
    while (s> 0) { 
        fichas.pop_front();
        s--;
    }
    for(int i = 0 ; i< columnas*filas; i++){
       tableroActual[i] = NULL;
       mejorTablero[i] = NULL;
       fichasM[i]  = NULL;
    }
    debugAux = NULL;
    comodinAux = NULL;    
}

void crearFichas(void) {
 
    comodinAux = new Shape(colores);
    comodinAux->comodin();
    debugAux = new Shape(colores);
    debugAux->debug();
    // fichasM.resize(filas*columnas);
    // Shape * s;
    // for (int i = 0; i < columnas * filas; i++) {
    //     s = new Shape(colores);
    //     fichasM[i] = s;
    //     s->randShape();
    //     fichas.push_back(s);
    // }
}

/*
 * 
 */
int main(int argc, char** argv) {
	char line[50];
    char* s_filas;
    char* s_columnas;
    char* s_colores;
    char* s_left;
    char* s_top;
    char* s_bottom;
    char* s_right;
	size_t pos = 0;
    int top,bottom,left,right;
	bool primerLinea = true;
    Shape * s;
    srand(time(NULL));
    Shape * actual;
    int l = 0;	
	while ( cin.getline(line,50) && line != "0" ){
		if (primerLinea){
			//Primer numero es filas
			s_filas = strtok(line," ");
            filas = atoi(s_filas);
            s_columnas = strtok(NULL," ");
            columnas = atoi(s_columnas);
			s_colores = strtok(NULL," ");
            colores = atoi(s_colores);
            fichasM.resize(filas*columnas);
        	primerLinea = false;
			continue;
		}
        s_left = strtok(line," ");
        left = atoi(s_left);
        s_top = strtok(NULL," ");
        top = atoi(s_top);
        s_right = strtok(NULL," ");
        right = atoi(s_right);
        s_bottom = strtok(NULL," ");
        bottom = atoi(s_bottom);
        
        s = new Shape(colores,left,top,right,bottom,l+1);
        //dbug("agreco %d",(l-1));
        fichasM[l] = s;
        fichas.push_back(s);        
        l++;
	}
    minIntentos = filas*columnas;
    crearFichas();
    crearTableros();
    actual = fichas.front();
    fichas.pop_front();
    posicionarFicha(&tableroActual, 0, actual);    
    intentosPorPosicion[0] = columnas * filas-1;
    calcularSolucion(1);    
    releaseShapes();
    //dbug("salgo\n");
    return 0;
}
